// https://www.luogu.com.cn/problem/P1048
#include <algorithm>
#include <cstdio>
using namespace std;
int rad();
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int maxn = 5 + 1e2;
int n, m;
struct Node {
    int p, v;
    double f;
} a[maxn];
int ans;

int sum_right(int dep, int nv) {
    int sum = 0;
    for (int i = dep; i <= n && nv <= m; ++i)
        sum += a[i].p, nv += a[i].v;
    return sum;
}

void dfs(int dep = 1, int np = 0, int nv = 0) {
    ans = max(ans, np);
    if (dep > n) return;
    if (nv + a[dep].v <= m) // 可行性剪枝
        dfs(dep + 1, np + a[dep].p, nv + a[dep].v);
    if (sum_right(dep + 1, nv) + np > ans) // 最优性剪枝
        dfs(dep + 1, np, nv);
}
int main() {
    scanf("%d%d", &m, &n);
    rf(i, n) a[i].v = rad(), a[i].p = rad(), a[i].f = (double)a[i].p / a[i].v;
    sort(a + 1, a + 1 + n, [](const Node &l, const Node &r) { return l.f > r.f; });
    dfs();
    printf("%d", ans);
}

int rad() {
    int back = 0, ch = 0;
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        back = back * 10 + (ch & 0xf), ch = getchar();
    return back;
}